package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode 22. 括号生成
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/13 9:33
 */
public class E22 {
    /*
       n = 1
       ()   1

       n = 2
       () (), (())    2

       n = 3
       () ()(), () (()), (())) (), (()()) (), ((())) ()    5

       n = 4

       (0子括号) 三括号组合，(1子括号) 二括号组合，(2子括号) 一括号组合， (3子括号) 0括号组合

       f(0) * f(3)  +  f(1) * f(2)  +  f(2) * f(1)  +  f(3) * f(0)

            5       +       2       +       2       +       5      =       14

     */

    /**
     * <h3>方法一：卡特兰数和动态规划，用的二维集合</h3>
     * @param n 括号对数
     * @return 所有可能的括号组合
     */
    public List<String> generateParenthesis1(int n) {
        List<List<String>> dp = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }
        dp.get(0).add("");
        dp.get(1).add("()");
        StringBuilder builder = new StringBuilder();
        // 将动态数组剩下的dp[i]填充
        for (int i = 2; i <= n; i++) {
            // 填充当前dp[i]的时候，取一个括号，分成里面inner和右边right继续加括号：(j个括号的组合)，i - 1 - j个括号的组合
            for (int j = 0; j < i; j++){
                List<String> inner = dp.get(j); // inner有j个括号，求j个括号的组合
                List<String> right = dp.get(i - 1 -j); // right有i - 1 - j个括号，求i - 1 - j个括号的组合
                for (String s : inner) { // 先选一个inner内的一种组合
                    for (String s1 : right) { // 再选一个right内的一种组合
                        dp.get(i).add(builder
                                .append("(")
                                .append(s)
                                .append(")")
                                .append(s1)
                                .toString()); // 组合
                        builder.setLength(0);
                    }
                }
            }
        }
        return dp.get(n);
    }

    /**
     * <h3>方法二：用dfs的思想进行穷举</h3>
     * @param n 括号对数
     * @return 所有可能的括号组合
     */
    public List<String> generateParenthesis2(int n) {
        List<String> result = new ArrayList<>();
        StringBuilder builder = new StringBuilder();
        dfs1(result, builder, n, 0, 0);
        return result;
    }

    /**
     * 递归实现函数
     * @param result 结果集
     * @param builder 括号字符串临时结果
     * @param n 括号对数
     * @param left 左括号数量
     * @param right 右括号数量
     */
    private void dfs1(List<String> result, StringBuilder builder, int n, int left, int right) {
        // 递归结束条件：左括号加右括号的数量等于2n
        if (left + right == n << 1){
            result.add(builder.toString());
            return;
        }
        // 递的时候如果左括号的数量小于n就继续加左括号
        if (left < n){
            builder.append("(");
            dfs1(result, builder, n, left + 1, right);
            // 归的时候删掉末尾括号
            builder.deleteCharAt(builder.length() - 1);
        }
        // 递的时候如果右括号的数量小于左括号的数量就继续加右括号,因为有(()())()这类情况
        if (right < left){
            builder.append(")");
            dfs1(result, builder, n, left, right + 1);
            // 归的时候删掉末尾括号
            builder.deleteCharAt(builder.length() - 1);
        }
    }

    /**
     * <h3>方法三：用dfs的思想进行穷举，用char数组优化StringBuilder</h3>
     * @param n 括号对数
     * @return 所有可能的括号组合
     */
    public List<String> generateParenthesis3(int n) {
        List<String> result = new ArrayList<>();
        char[] builder = new char[n << 1]; // 存放括号字符串
        dfs2(result, builder, n, 0, 0);
        return result;
    }

    /**
     * 递归实现函数
     * @param result 结果集
     * @param builder 括号字符串临时结果
     * @param n 括号对数
     * @param left 左括号数量
     * @param right 右括号数量
     */
    private void dfs2(List<String> result, char[] builder, int n, int left, int right) {
        // 递归结束条件：左括号加右括号的数量等于2n
        if (left + right == n << 1){
            result.add(String.valueOf(builder));
            return;
        }
        // 递的时候如果左括号的数量小于n就继续加左括号
        if (left < n){
            builder[left + right] = '(';
            dfs2(result, builder, n, left + 1, right);
            // 归的时候删掉末尾括号，归的时候builder末尾指针left + right会自然回溯
        }
        // 递的时候如果右括号的数量小于左括号的数量就继续加右括号,因为有(()())()这类情况
        if (right < left){
            builder[left + right] = ')';
            dfs2(result, builder, n, left, right + 1);
            // 归的时候删掉末尾括号，归的时候builder末尾指针left + right会自然回溯
        }
    }
}
